/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-18
 * Time: 9:04
 */
public class Solution {
    /**
     * 方法一: 根据左右两边的数字个数判断在哪个区间
     * @param nums
     * @return
     */
    public int singleNonDuplicate(int[] nums) {
        int len = nums.length;
        int left = 0;
        int right = len - 1;
        while (left <= right){
            int mid = (left + right) >> 1;
            // 只剩下一个元素 或者与左右两边的值都不相等 就是结果
            if (mid == left ||
                    (mid - 1) >= left && (mid + 1) <= right
                            && nums[mid - 1] != nums[mid] && nums[mid + 1] != nums[mid]){
                return nums[mid];
            }
            // 至少与左右两边其中一个值相等

            // 与左边的值相等
            if ((mid - 1) >= left && nums[mid - 1] == nums[mid]) {
                // 判断左右两边的数字的个数
                if ((mid - left) % 2 == 1){
                    left = mid + 1;
                }else{
                    right = mid;
                }
            }else{
                // 与右边的值相等

                // 判断左右两边的数字的个数
                if ((right - mid) % 2 == 1){
                    right = mid - 1;
                }else{
                    left = mid;
                }
            }
        }
        return -1;
    }


    /**
     *  方法二:
     * @param nums
     * @return
     */
    public int singleNonDuplicate2(int[] nums) {
        int len = nums.length;
        int left = 0;
        int right = len - 1;
        while (left < right){
//             [left, right] 这个区间包含的元素个数一定是 奇数个
//             那么就决定了 mid 的位置, 因为 Mid 要么是奇数, 要么是偶数
//             所以当 mid 为奇数, 比较 mid 和 mid - 1 下标对应的元素是否相等
//             所以当 mid 为偶数, 比较 mid 和 mid + 1 下标对应的元素是否相等
//             这两种情况下, 只要相等, 结果就在右边的区间
//             又因为 mid 为偶数时  mid + 1 == mid ^ 1
//             又因为 mid 为奇数时  mid - 1 == mid ^ 1
//             所以不用再判断 Mid 的奇偶性了, 直接比较对应的值即可
            int mid = (left + right) >> 1;
            if (nums[mid] == nums[mid ^ 1]){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return nums[left];
    }
}
